<!Doctype html>
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
	<meta name="viewport" content="width=device-width, initial-scale=1.0" />
	<title>1.9 桶排序 | 菜鸟教程</title>

  <meta name='robots' content='max-image-preview:large' />
<link rel='stylesheet' id='classic-theme-styles-css' href='../0/classic-themes.min.css?ver=6.2' type='text/css' media='all' />
<link rel="canonical" href="../w3cnote/bucket-sort.html" />
<meta name="keywords" content="1.9 桶排序">
<meta name="description" content="桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：  在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中  同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。  1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。  2. 什么时候最慢 当输入的数据被分配到了同一个桶中。 3..">
		
	<link rel="shortcut icon" href="https://static.runoob.com/images/favicon.ico">
	<link rel="stylesheet" href="../0/style.css?v=1.170" type="text/css" media="all" />	
	<link rel="stylesheet" href="../0/font-awesome.min.css" media="all" />	
  <!--[if gte IE 9]><!-->
  <script src=""></script>
  <!--<![endif]-->
  <!--[if lt IE 9]>
     <script src=""></script>
     <script src=""></script>
  <![endif]-->
  <link rel="apple-touch-icon" href="https://static.runoob.com/images/icon/mobile-icon.png"/>
  <meta name="apple-mobile-web-app-title" content="菜鸟教程">
</head>
<body>

<!--  头部 -->
<div class="container logo-search">

  <div class="col search row-search-mobile">
    <form action="index.php">
      <input class="placeholder" placeholder="搜索……" name="s" autocomplete="off">
      
    </form>
  </div>

  <div class="row">
    <div class="col logo">
      <h1><a href="../">菜鸟教程 -- 学的不仅是技术，更是梦想！</a></h1>
    </div>
        <div class="col right-list"> 
    <button class="btn btn-responsive-nav btn-inverse" data-toggle="collapse" data-target=".nav-main-collapse" id="pull" style=""> <i class="fa fa-navicon"></i> </button>
    </div>
        
    <div class="col search search-desktop last">
      <div class="search-input" >
      <form action="//www.runoob.com/" target="_blank">
        <input class="placeholder" id="s" name="s" placeholder="搜索……"  autocomplete="off" style="height: 44px;">
      </form>
      
      </div>
    </div>
  </div>
</div>



<!-- 导航栏 -->
<div class="container navigation">
    <div class="row">
        <div class="col nav">
            

                        <ul class="pc-nav" id="note-nav">
                <li><a href="../">首页</a></li>
                <li><a href="../w3cnote">笔记首页</a></li>
                <li><a href="../w3cnote/android-tutorial-intro.html" title="Android 基础入门教程">Android</a></li>
                <li><a href="../w3cnote/es6-tutorial.html" title="ES6 教程">ES6 教程</a></li>
                <li><a href="../w3cnote/ten-sorting-algorithm.html" title="排序算法">排序算法</a></li>
                <li><a href="../w3cnote/hadoop-tutorial.html" title="Hadoop 教程">Hadoop</a></li>
                <li><a href="../w3cnote/zookeeper-tutorial.html" title="Zookeeper 教程">Zookeeper</a></li>
                <li><a href="../w3cnote/verilog-tutorial.html" title="Verilog 教程">Verilog</a></li>
                <li><a href="../w3cnote_genre/code" title="编程技术">编程技术</a></li> 
                <li><a href="../w3cnote_genre/coderlife" title="程序员人生">程序员人生</a></li>
                
                <!--<li><a href="javascript:;" class="runoob-pop">登录</a></li>
                
                
                        <li>
                <a style="font-weight:bold;" href="../linux/linux-tutorial.html#yunserver" target="_blank" onclick="_hmt.push(['_trackEvent', 'aliyun', 'click', 'aliyun'])" title="kkb">云服务器</a>
                </li>
                <li><a href="http://gk.link/a/104mQ" target="_blank" style="font-weight: bold;"onclick="_hmt.push(['_trackEvent', '极客时间', 'click', 'jike'])" title="我的圈子">极客时间</a></li>
            
                
                <li><a target="_blank" href="../shoppinglist" rel="nofollow">知识店铺</a></li> 
        -->
            </ul>
                        
              
            <ul class="mobile-nav">
                <li><a href="../w3cnote">首页</a></li>
                <li><a href="../w3cnote_genre/android" target="_blank" title="Android 基础入门教程">Android</a></li>
                <li><a href="../w3cnote/es6-tutorial.html" target="_blank" title="ES6 教程">ES6</a></li>
                <li><a href="../w3cnote_genre/joke" target="_blank" title="程序员笑话">逗乐</a></li>
                
                <a href="javascript:void(0)" class="search-reveal">Search</a> 
            </ul>
            
        </div>
    </div>
</div>


<!--  内容  -->
<div class="container main">
	<div class="row">

		<div class="col middle-column big-middle-column">
	 			<div class="article">
			<div class="article-heading">
				<h2>1.9 桶排序</h2>				<h3><em>分类</em> <a href="../w3cnote_genre/algorithm" title="算法" >算法</a> </h3>
			</div>
			<div class="article-body note-body">
				<div class="article-intro">
					<p>桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：</p>
<ol>
<li>在额外空间充足的情况下，尽量增大桶的数量</li>
<li>使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中</li>
</ol>
<p>同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。</p>

<h3>1. 什么时候最快</h3>
<p>当输入的数据可以均匀的分配到每一个桶中。</p>

<h3>2. 什么时候最慢</h3>
<p>当输入的数据被分配到了同一个桶中。</p>
<h3>3. 示意图</h3>
<p>元素分布在桶中：</p>
<p><img decoding="async" src="//www.runoob.com/wp-content/uploads/2019/03/Bucket_sort_1.svg_.png"  /></p>
<p>然后，元素在每个桶中排序：</p>
<p><img decoding="async" src="//www.runoob.com/wp-content/uploads/2019/03/Bucket_sort_2.svg_.png"  /></p>
<hr><h2>代码实现</h2>
<h3>JavaScript</h3>
<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #000066; font-weight: bold;">function</span> bucketSort<span style="color: #009900;">&#40;</span>arr<span style="color: #339933;">,</span> bucketSize<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>arr.<span style="color: #660066;">length</span> <span style="color: #339933;">===</span> <span style="color: #CC0000;">0</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> i<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> minValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span><span style="color: #CC0000;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> maxValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span><span style="color: #CC0000;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #CC0000;">1</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> arr.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span> <span style="color: #339933;">&lt;</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="color: #006600; font-style: italic;">// 输入数据的最小值</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span> <span style="color: #000066; font-weight: bold;">else</span> <span style="color: #000066; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span> <span style="color: #339933;">&gt;</span> maxValue<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="color: #006600; font-style: italic;">// 输入数据的最大值</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #006600; font-style: italic;">//桶的初始化</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> DEFAULT_BUCKET_SIZE <span style="color: #339933;">=</span> <span style="color: #CC0000;">5</span><span style="color: #339933;">;</span> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="color: #006600; font-style: italic;">// 设置桶的默认数量为5</span><br />
&nbsp; &nbsp; bucketSize <span style="color: #339933;">=</span> bucketSize <span style="color: #339933;">||</span> DEFAULT_BUCKET_SIZE<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> bucketCount <span style="color: #339933;">=</span> <span style="">Math</span>.<span style="color: #660066;">floor</span><span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>maxValue <span style="color: #339933;">-</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> bucketSize<span style="color: #009900;">&#41;</span> <span style="color: #339933;">+</span> <span style="color: #CC0000;">1</span><span style="color: #339933;">;</span> &nbsp; <br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> buckets <span style="color: #339933;">=</span> <span style="color: #000066; font-weight: bold;">new</span> <span style="">Array</span><span style="color: #009900;">&#40;</span>bucketCount<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> buckets.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; buckets<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> <span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #006600; font-style: italic;">//利用映射函数将数据分配到各个桶中</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> arr.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; buckets<span style="color: #009900;">&#91;</span><span style="">Math</span>.<span style="color: #660066;">floor</span><span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span> <span style="color: #339933;">-</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> bucketSize<span style="color: #009900;">&#41;</span><span style="color: #009900;">&#93;</span>.<span style="color: #660066;">push</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; arr.<span style="color: #660066;">length</span> <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> buckets.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; insertionSort<span style="color: #009900;">&#40;</span>buckets<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="color: #006600; font-style: italic;">// 对每个桶进行排序，这里使用了插入排序</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">var</span> j <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> j <span style="color: #339933;">&lt;</span> buckets<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span>.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> j<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr.<span style="color: #660066;">push</span><span style="color: #009900;">&#40;</span>buckets<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
<span style="color: #009900;">&#125;</span><br />
</div></div>

<h3>Java</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000000; font-weight: bold;">class</span> BucketSort <span style="color: #000000; font-weight: bold;">implements</span> IArraySort <span style="color: #009900;">&#123;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000000; font-weight: bold;">static</span> <span style="color: #000000; font-weight: bold;">final</span> InsertSort insertSort <span style="color: #339933;">=</span> <span style="color: #000000; font-weight: bold;">new</span> InsertSort<span style="color: #009900;">&#40;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; @Override<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> sort<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> sourceArray<span style="color: #009900;">&#41;</span> <span style="color: #000000; font-weight: bold;">throws</span> <span style="color: #003399;">Exception</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666; font-style: italic;">// 对 arr 进行拷贝，不改变参数内容</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr <span style="color: #339933;">=</span> <span style="color: #003399;">Arrays</span>.<span style="color: #006633;">copyOf</span><span style="color: #009900;">&#40;</span>sourceArray, sourceArray.<span style="color: #006633;">length</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> bucketSort<span style="color: #009900;">&#40;</span>arr, <span style="color: #cc66cc;">5</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> bucketSort<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr, <span style="color: #000066; font-weight: bold;">int</span> bucketSize<span style="color: #009900;">&#41;</span> <span style="color: #000000; font-weight: bold;">throws</span> <span style="color: #003399;">Exception</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>arr.<span style="color: #006633;">length</span> <span style="color: #339933;">==</span> <span style="color: #cc66cc;">0</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> minValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> maxValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> value <span style="color: #339933;">:</span> arr<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>value <span style="color: #339933;">&lt;</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minValue <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span> <span style="color: #000000; font-weight: bold;">else</span> <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>value <span style="color: #339933;">&gt;</span> maxValue<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxValue <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> bucketCount <span style="color: #339933;">=</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#41;</span> <span style="color: #003399;">Math</span>.<span style="color: #006633;">floor</span><span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>maxValue <span style="color: #339933;">-</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> bucketSize<span style="color: #009900;">&#41;</span> <span style="color: #339933;">+</span> <span style="color: #cc66cc;">1</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> buckets <span style="color: #339933;">=</span> <span style="color: #000000; font-weight: bold;">new</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span>bucketCount<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#91;</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666; font-style: italic;">// 利用映射函数将数据分配到各个桶中</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> i <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> arr.<span style="color: #006633;">length</span><span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> index <span style="color: #339933;">=</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#41;</span> <span style="color: #003399;">Math</span>.<span style="color: #006633;">floor</span><span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span> <span style="color: #339933;">-</span> minValue<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> bucketSize<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; buckets<span style="color: #009900;">&#91;</span>index<span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> arrAppend<span style="color: #009900;">&#40;</span>buckets<span style="color: #009900;">&#91;</span>index<span style="color: #009900;">&#93;</span>, arr<span style="color: #009900;">&#91;</span>i<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> arrIndex <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> bucket <span style="color: #339933;">:</span> buckets<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>bucket.<span style="color: #006633;">length</span> <span style="color: #339933;">&lt;=</span> <span style="color: #cc66cc;">0</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">continue</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666; font-style: italic;">// 对每个桶进行排序，这里使用了插入排序</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bucket <span style="color: #339933;">=</span> insertSort.<span style="color: #006633;">sort</span><span style="color: #009900;">&#40;</span>bucket<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> value <span style="color: #339933;">:</span> bucket<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #009900;">&#91;</span>arrIndex<span style="color: #339933;">++</span><span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #008000; font-style: italic; font-weight: bold;">/**<br />
&nbsp; &nbsp; &nbsp;* 自动扩容，并保存数据<br />
&nbsp; &nbsp; &nbsp;*<br />
&nbsp; &nbsp; &nbsp;* @param arr<br />
&nbsp; &nbsp; &nbsp;* @param value<br />
&nbsp; &nbsp; &nbsp;*/</span><br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arrAppend<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr, <span style="color: #000066; font-weight: bold;">int</span> value<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; arr <span style="color: #339933;">=</span> <span style="color: #003399;">Arrays</span>.<span style="color: #006633;">copyOf</span><span style="color: #009900;">&#40;</span>arr, arr.<span style="color: #006633;">length</span> <span style="color: #339933;">+</span> <span style="color: #cc66cc;">1</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #009900;">&#91;</span>arr.<span style="color: #006633;">length</span> <span style="color: #339933;">-</span> <span style="color: #cc66cc;">1</span><span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
<span style="color: #009900;">&#125;</span><br />
</div></div>

<h3>PHP</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #000000; ">function</span> bucketSort<span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #000000;">,</span> <span style="color: #05a;">$bucketSize</span> <span style="color: #000000;">=</span> <span style="color: #164;">5</span><span style="color: #164;">&#41;</span><br />
<span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#41;</span> <span style="color: #000000;">===</span> <span style="color: #164;">0</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #708;">return</span> <span style="color: #05a;">$arr</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #05a;">$minValue</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #164;">0</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">$maxValue</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #164;">0</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$i</span> <span style="color: #000000;">=</span> <span style="color: #164;">1</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">&lt;</span> <span style="color: #05a;">$minValue</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$minValue</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span> <span style="color: #708;">else</span> <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">&gt;</span> <span style="color: #05a;">$maxValue</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$maxValue</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #05a;">$bucketCount</span> <span style="color: #000000;">=</span> <span style="color: #990000;">floor</span><span style="color: #164;">&#40;</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$maxValue</span> <span style="color: #000000;">-</span> <span style="color: #05a;">$minValue</span><span style="color: #164;">&#41;</span> <span style="color: #000000;">/</span> <span style="color: #05a;">$bucketSize</span><span style="color: #164;">&#41;</span> <span style="color: #000000;">+</span> <span style="color: #164;">1</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">$buckets</span> <span style="color: #000000;">=</span> <span style="color: #990000;">array</span><span style="color: #164;">&#40;</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$i</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">&lt;</span> <span style="color: #05a;">$bucketCount</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$buckets</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$i</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$buckets</span><span style="color: #164;">&#91;</span><span style="color: #990000;">floor</span><span style="color: #164;">&#40;</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">-</span> <span style="color: #05a;">$minValue</span><span style="color: #164;">&#41;</span> <span style="color: #000000;">/</span> <span style="color: #05a;">$bucketSize</span><span style="color: #164;">&#41;</span><span style="color: #164;">&#93;</span><span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #05a;">$arr</span> <span style="color: #000000;">=</span> <span style="color: #990000;">array</span><span style="color: #164;">&#40;</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$i</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$buckets</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$bucketTmp</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$buckets</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$i</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #990000;">sort</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$bucketTmp</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$j</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$bucketTmp</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$bucketTmp</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$j</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">return</span> <span style="color: #05a;">$arr</span><span style="color: #000000;">;</span><br />
<span style="color: #164;">&#125;</span><br />
</div></div>


<h3>C++</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #060;">#include&lt;iterator&gt;</span><br />
<span style="color: #060;">#include&lt;iostream&gt;</span><br />
<span style="color: #060;">#include&lt;vector&gt;</span><br />
<span style="color: #05a;">using</span> <span style="color: #05a;">namespace</span> std<span style="color: #008080;">;</span><br />
<span style="color: #05a;">const</span> <span style="color: #05a;">int</span> BUCKET_NUM <span style="color: #000080;">=</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span><br />
<br />
<span style="color: #05a;">struct</span> ListNode<span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">explicit</span> ListNode<span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> i<span style="color: #000080;">=</span><span style="color: #0000dd;">0</span><span style="color: #008000;">&#41;</span><span style="color: #008080;">:</span>mData<span style="color: #008000;">&#40;</span>i<span style="color: #008000;">&#41;</span>,mNext<span style="color: #008000;">&#40;</span><span style="color: #05a;">NULL</span><span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode<span style="color: #000040;">*</span> mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">int</span> mData<span style="color: #008080;">;</span><br />
<span style="color: #008000;">&#125;</span><span style="color: #008080;">;</span><br />
<br />
ListNode<span style="color: #000040;">*</span> insert<span style="color: #008000;">&#40;</span>ListNode<span style="color: #000040;">*</span> head,<span style="color: #05a;">int</span> val<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode dummyNode<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode <span style="color: #000040;">*</span>newNode <span style="color: #000080;">=</span> <span style="color: #05a;">new</span> ListNode<span style="color: #008000;">&#40;</span>val<span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode <span style="color: #000040;">*</span>pre,<span style="color: #000040;">*</span>curr<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; dummyNode.<span style="color: #007788;">mNext</span> <span style="color: #000080;">=</span> head<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; pre <span style="color: #000080;">=</span> <span style="color: #000040;">&amp;</span>dummyNode<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; curr <span style="color: #000080;">=</span> head<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">while</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">NULL</span><span style="color: #000040;">!</span><span style="color: #000080;">=</span>curr <span style="color: #000040;">&amp;&amp;</span> curr<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mData<span style="color: #000080;">&lt;=</span>val<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pre <span style="color: #000080;">=</span> curr<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; curr <span style="color: #000080;">=</span> curr<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; newNode<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> curr<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; pre<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> newNode<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">return</span> dummyNode.<span style="color: #007788;">mNext</span><span style="color: #008080;">;</span><br />
<span style="color: #008000;">&#125;</span><br />
<br />
<br />
ListNode<span style="color: #000040;">*</span> Merge<span style="color: #008000;">&#40;</span>ListNode <span style="color: #000040;">*</span>head1,ListNode <span style="color: #000040;">*</span>head2<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode dummyNode<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode <span style="color: #000040;">*</span>dummy <span style="color: #000080;">=</span> <span style="color: #000040;">&amp;</span>dummyNode<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">while</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">NULL</span><span style="color: #000040;">!</span><span style="color: #000080;">=</span>head1 <span style="color: #000040;">&amp;&amp;</span> <span style="color: #05a;">NULL</span><span style="color: #000040;">!</span><span style="color: #000080;">=</span>head2<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">if</span><span style="color: #008000;">&#40;</span>head1<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mData <span style="color: #000080;">&lt;=</span> head2<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mData<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dummy<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> head1<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; head1 <span style="color: #000080;">=</span> head1<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><span style="color: #05a;">else</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dummy<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> head2<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; head2 <span style="color: #000080;">=</span> head2<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dummy <span style="color: #000080;">=</span> dummy<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">if</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">NULL</span><span style="color: #000040;">!</span><span style="color: #000080;">=</span>head1<span style="color: #008000;">&#41;</span> dummy<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> head1<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">if</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">NULL</span><span style="color: #000040;">!</span><span style="color: #000080;">=</span>head2<span style="color: #008000;">&#41;</span> dummy<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext <span style="color: #000080;">=</span> head2<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">return</span> dummyNode.<span style="color: #007788;">mNext</span><span style="color: #008080;">;</span><br />
<span style="color: #008000;">&#125;</span><br />
<br />
<span style="color: #05a;">void</span> BucketSort<span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> n,<span style="color: #05a;">int</span> arr<span style="color: #008000;">&#91;</span><span style="color: #008000;">&#93;</span><span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; vector<span style="color: #000080;">&lt;</span>ListNode<span style="color: #000040;">*</span><span style="color: #000080;">&gt;</span> buckets<span style="color: #008000;">&#40;</span>BUCKET_NUM,<span style="color: #008000;">&#40;</span>ListNode<span style="color: #000040;">*</span><span style="color: #008000;">&#41;</span><span style="color: #008000;">&#40;</span><span style="color: #0000dd;">0</span><span style="color: #008000;">&#41;</span><span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> i<span style="color: #000080;">=</span><span style="color: #0000dd;">0</span><span style="color: #008080;">;</span>i<span style="color: #000080;">&lt;</span>n<span style="color: #008080;">;</span><span style="color: #000040;">++</span>i<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">int</span> index <span style="color: #000080;">=</span> arr<span style="color: #008000;">&#91;</span>i<span style="color: #008000;">&#93;</span><span style="color: #000040;">/</span>BUCKET_NUM<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ListNode <span style="color: #000040;">*</span>head <span style="color: #000080;">=</span> buckets.<span style="color: #007788;">at</span><span style="color: #008000;">&#40;</span>index<span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; buckets.<span style="color: #007788;">at</span><span style="color: #008000;">&#40;</span>index<span style="color: #008000;">&#41;</span> <span style="color: #000080;">=</span> insert<span style="color: #008000;">&#40;</span>head,arr<span style="color: #008000;">&#91;</span>i<span style="color: #008000;">&#93;</span><span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; ListNode <span style="color: #000040;">*</span>head <span style="color: #000080;">=</span> buckets.<span style="color: #007788;">at</span><span style="color: #008000;">&#40;</span><span style="color: #0000dd;">0</span><span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> i<span style="color: #000080;">=</span><span style="color: #0000dd;">1</span><span style="color: #008080;">;</span>i<span style="color: #000080;">&lt;</span>BUCKET_NUM<span style="color: #008080;">;</span><span style="color: #000040;">++</span>i<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; head <span style="color: #000080;">=</span> Merge<span style="color: #008000;">&#40;</span>head,buckets.<span style="color: #007788;">at</span><span style="color: #008000;">&#40;</span>i<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> i<span style="color: #000080;">=</span><span style="color: #0000dd;">0</span><span style="color: #008080;">;</span>i<span style="color: #000080;">&lt;</span>n<span style="color: #008080;">;</span><span style="color: #000040;">++</span>i<span style="color: #008000;">&#41;</span><span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #008000;">&#91;</span>i<span style="color: #008000;">&#93;</span> <span style="color: #000080;">=</span> head<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mData<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; head <span style="color: #000080;">=</span> head<span style="color: #000040;">-</span><span style="color: #000080;">&gt;</span>mNext<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
<span style="color: #008000;">&#125;</span><br />
</div></div>



<blockquote><p>参考地址：</p>
<p>https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/9.bucketSort.md</p>
<p>https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F</p></blockquote>

				</div>
			</div>
			<div class="previous-next-links">
			<div class="previous-design-link">← <a href="../w3cnote/counting-sort.html" rel="prev"> 1.8 计数排序</a> </div>
			<div class="next-design-link"><a href="../w3cnote/radix-sort.html" rel="next"> 1.10 基数排序</a> →</div>
			</div>
			<style>
.wrapper {
  /*text-transform: uppercase; */
  background: #ececec;
  color: #555;
  cursor: help;
  font-family: "Gill Sans", Impact, sans-serif;
  font-size: 20px;
  position: relative;
  text-align: center;
  width: 200px;
  -webkit-transform: translateZ(0); /* webkit flicker fix */
  -webkit-font-smoothing: antialiased; /* webkit text rendering fix */
}

.wrapper .tooltip {
  white-space: nowrap;
  font-size: 14px;
  text-align: left;
  background: #96b97d;
  bottom: 100%;
  color: #fff;
  display: block;
  left: -25px;
  margin-bottom: 15px;
  opacity: 0;
  padding: 14px;
  pointer-events: none;
  position: absolute;
  
  -webkit-transform: translateY(10px);
     -moz-transform: translateY(10px);
      -ms-transform: translateY(10px);
       -o-transform: translateY(10px);
          transform: translateY(10px);
  -webkit-transition: all .25s ease-out;
     -moz-transition: all .25s ease-out;
      -ms-transition: all .25s ease-out;
       -o-transition: all .25s ease-out;
          transition: all .25s ease-out;
  -webkit-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
     -moz-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
      -ms-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
       -o-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
          box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
}
.tooltip a {
	color:#fff;
}
/* This bridges the gap so you can mouse into the tooltip without it disappearing */
.wrapper .tooltip:before {
  bottom: -20px;
  content: " ";
  display: block;
  height: 20px;
  left: 0;
  position: absolute;
  width: 100%;
}  

/* CSS Triangles - see Trevor's post */
.wrapper .tooltip:after {
  border-left: solid transparent 10px;
  border-right: solid transparent 10px;
  border-top: solid #96b97d 10px;
  bottom: -10px;
  content: " ";
  height: 0;
  left: 20%;
  margin-left: -13px;
  position: absolute;
  width: 0;
}
.wrapper .tooltip1 {
	margin-left: 50px;
	padding-top: 0px;
}
/*
.wrapper:hover .tooltip {
  opacity: 1;
  pointer-events: auto;
  -webkit-transform: translateY(0px);
     -moz-transform: translateY(0px);
      -ms-transform: translateY(0px);
       -o-transform: translateY(0px);
          transform: translateY(0px);
}
*/
/* IE can just show/hide with no transition */
.lte8 .wrapper .tooltip {
  display: none;
}

.lte8 .wrapper:hover .tooltip {
  display: block;
}

</style>

<link rel="stylesheet" href="../0/upvotejs.css">
<script src=""></script>
<script src=""></script>
<div class="title" id="comments">
	<h2 class="">
    <div class="altblock">
				<i style="font-size:28px;margin-top: 8px;" class="fa fa-plus-square" aria-hidden="true"></i>
		    </div>
    <span class="mw-headline" id="qa_headline">3  篇笔记</span>
	<span class="mw-headline" id="user_add_note" style="float:right;line-height: 62px;padding-right: 14px;"><i class="fa fa-pencil-square-o" aria-hidden="true"></i>  写笔记</span>
    </h2>
</div>

<div id="postcomments"  style="display:none;" >
	<ol class="commentlist">
		<li class="comment even thread-even depth-1" id="comment-55742"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;zihe.zhu</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;zih***hu@qq.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://github.com/IamHehe/TrySort/blob/master/9.bucket_sort.py">&nbsp;&nbsp;参考地址</a></p></div><div id="runoobvote-id-55742" data-commid = "55742" class="upvotejs"><a class="upvote"></a> <span class="count">21</span></div></div><div class="comt-main" id="div-comment-55742"><pre># coding=utf-8
# author: dl.zihezhu@gmail.com
# datetime:2020/7/28 18:37

"""
程序说明：
    桶排序
    1）在额外空间充足的情况下，尽量增大桶的数量
    2）使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
      个人理解，如果都是整数还可以用计数排序来计数统计然后排序，但是如果是一个连续空间内的排序，即统计的是一个浮点类型的数组成
      的数组，那么，就无法开辟一个对应的空间使其一一对应的存储。此时，我们需要新建一个带有存储范围的空间，来存储一定范围内的元素
    空间复杂度：O(n)
    时间复杂度: O(n)
    稳定
"""


def bucket_sort_simplify(arr, max_num):
    """
    简化版
    """
    buf = {i: [] for i in range(int(max_num)+1)}  # 不能使用[[]]*(max+1)，这样新建的空间中各个[]是共享内存的
    arr_len = len(arr)
    for i in range(arr_len):
        num = arr[i]
        buf[int(num)].append(num)  # 将相应范围内的数据加入到[]中
    arr = []
    for i in range(len(buf)):
        if buf[i]:
            arr.extend(sorted(buf[i]))  # 这里还需要对一个范围内的数据进行排序，然后再进行输出
    return arr


if __name__ == "__main__":
    lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
    print(bucket_sort_simplify(lis, max(lis)))</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">zihe.zhu</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;zihe.zhu</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;zih***hu@qq.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://github.com/IamHehe/TrySort/blob/master/9.bucket_sort.py">&nbsp;&nbsp;参考地址</a></p></div></span>3年前 (2020-07-28)</div></div></li><!-- #comment-## -->
<li class="comment odd alt thread-odd thread-alt depth-1" id="comment-57613"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;艾孜尔江</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;bju***ft@sina.com</p></div><div id="runoobvote-id-57613" data-commid = "57613" class="upvotejs"><a class="upvote"></a> <span class="count">25</span></div></div><div class="comt-main" id="div-comment-57613"><p>又没把C#的写进来，我来写掉吧，代码如下：</p>

<pre>static void BucketSort(List&lt;int&gt; list, int bucketCount, int maxBucketCount)
{
    List&lt;List&lt;int&gt;&gt; buckets = new List&lt;List&lt;int&gt;&gt;(bucketCount);//二维列表
    for (int i = 0; i &lt; bucketCount; i++)
    {
        buckets.Add(new List&lt;int&gt;());
    }
    for (int i = 0; i &lt; list.Count; i++)
    {
        // int j = Mathf.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪个桶,不能大于n-1
        int j = Math.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪个桶,不能大于n-1
        buckets[j].Add(list[i]);//放入对应桶
        for (int x = buckets[j].Count - 1; x &gt; 0; x--)//放一个排序一次，两两对比就可以
        {
            if (buckets[j][x] &lt; buckets[j][x - 1])//升序
            {
                int tmp = buckets[j][x];//交换
                buckets[j][x] = buckets[j][x - 1];
                buckets[j][x - 1] = tmp;
            }
            else
            {
                break;//如果不发生交换直接退出，因为前面的之前就排序好了
            }
        }
    }
    list.Clear();//输出
    for (int i = 0; i &lt; buckets.Count; i++)
    {
        list.AddRange(buckets[i]);
    }
}</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">艾孜尔江</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;艾孜尔江</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;bju***ft@sina.com</p></div></span>3年前 (2020-10-08)</div></div></li><!-- #comment-## -->
<li class="comment even thread-even depth-1" id="comment-72010"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;iEngne</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;sep***n@foxmail.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://raw.githubusercontent.com/iEngne/algorithm_practice/master/sort/bucket_sort.c">&nbsp;&nbsp;参考地址</a></p></div><div id="runoobvote-id-72010" data-commid = "72010" class="upvotejs"><a class="upvote"></a> <span class="count">0</span></div></div><div class="comt-main" id="div-comment-72010"><p>C 语言实现桶排序，桶内采用插入排序:</p>

<pre>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;


#define BUCKET_SIZE (5) /**&lt; 假定均匀分布的情况下平均每个桶放几个元素*/


typedef struct Node
{
    int elem;
    struct Node* list_next;
} Node;

typedef struct BucketManager
{
    int nums;
    Node** buckets;  
} BucketManager;

typedef struct BucketSpaceManager
{
    int index;
    Node* nodes_space;
} BucketSpaceManager;


BucketSpaceManager* init_bucket_space(int size)
{
    BucketSpaceManager* space_mgr = (BucketSpaceManager*)malloc(sizeof(BucketSpaceManager));
    if (!space_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }
    space_mgr-&gt;index = 0;
    space_mgr-&gt;nodes_space = (Node*)malloc(size * sizeof(Node));
    if (!space_mgr-&gt;nodes_space)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_2;
    }

    return space_mgr;

exit_2:
    free(space_mgr);
exit_1:
    return NULL;
}


BucketManager* init_buckets(int bucket_nums)
{
    BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager));
    if (!bucket_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }
    bucket_mgr-&gt;nums = bucket_nums;
    bucket_mgr-&gt;buckets = (Node**)calloc(bucket_mgr-&gt;nums, sizeof(Node*));
    if (!bucket_mgr-&gt;buckets)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_2;
    }
    return bucket_mgr;
exit_2:
    free(bucket_mgr);
exit_1:
    return NULL;
}


Node* get_bucket_space(BucketSpaceManager* space_mgr)
{
    if (space_mgr)
    {
        return &amp;space_mgr-&gt;nodes_space[space_mgr-&gt;index++];
    }
    else
    {
        return NULL;
    }
}


void release_bucket_space(BucketSpaceManager* space_mgr)
{
    if (space_mgr)
    {
        if (space_mgr-&gt;nodes_space)
        {
            free(space_mgr-&gt;nodes_space);
        }
        free(space_mgr);
    }
}


void release_buckets(BucketManager* buckets_mgr)
{
    if (buckets_mgr)
    {
        if (buckets_mgr-&gt;buckets)
        {
            free(buckets_mgr-&gt;buckets);
        }
        free(buckets_mgr);
    }
}

int find_max_min(int* arr, int size, int* p_max, int* p_min)
{
    if (size &lt;= 0)
    {
        return -1;
    }
    *p_max = arr[0];
    *p_min = arr[0];
    int i;
    for (i = 1; i &lt; size; ++i)
    {
        if (arr[i] &gt; *p_max)
        {
            *p_max = arr[i];
        }
        if (arr[i] &lt; *p_min)
        {
            *p_min = arr[i];
        }
    }
    return 0;
}


int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node)
{
    Node* cur, *pre;
    if (!bucket_mgr-&gt;buckets[index])
    {
        bucket_mgr-&gt;buckets[index] = new_node;
    }
    else
    {
        /** 桶内使用插入排序 */
        cur = bucket_mgr-&gt;buckets[index];
        pre = cur;
        while (cur-&gt;list_next &amp;&amp; new_node-&gt;elem &gt; cur-&gt;elem)
        {
            pre = cur;
            cur = cur-&gt;list_next;
        }

        if (new_node-&gt;elem &lt;= cur-&gt;elem)
        {
            if (pre == cur)
            {
                new_node-&gt;list_next = cur;
                bucket_mgr-&gt;buckets[index] = new_node;
            }
            else
            {
                new_node-&gt;list_next = cur;
                pre-&gt;list_next = new_node;
            }
        }
        else
        {
            cur-&gt;list_next = new_node;
        }

    }
    return 0;
}


void bucket_sort(int* arr, int size)
{
    int max, min;
    int ret = find_max_min(arr, size, &amp;max, &amp;min);
    if (ret &lt; 0)
    {
        return;
    }

    BucketSpaceManager* space_mgr = init_bucket_space(size);
    if (!space_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }

    int bucket_nums = (max - min) / BUCKET_SIZE + 1;
    BucketManager* bucket_mgr = init_buckets(bucket_nums);
    if (!bucket_mgr)
    {
        goto exit_2;
    }
    int i;
    for (i = 0; i &lt; size; ++i)
    {
        int index = (arr[i] - min) / BUCKET_SIZE;
        Node* new_node = get_bucket_space(space_mgr);
        if (!new_node)
        {
            goto exit_3;
        }
        new_node-&gt;elem = arr[i];
        new_node-&gt;list_next = NULL;
        insert_bucket(bucket_mgr, index, new_node);
    }
    for (i = 0; i &lt; bucket_mgr-&gt;nums; ++i)
    {
        Node* node = bucket_mgr-&gt;buckets[i];
        while(node)
        {
            printf("%d ", node-&gt;elem);
            node = node-&gt;list_next;
        }
    }
    printf("\n");
exit_3:
    release_buckets(bucket_mgr);
exit_2:
    release_bucket_space(space_mgr);
exit_1:
    return;
}</pre>
<p><a class="download" download href="https://static.runoob.com/code/c/bucket_sort.c" target="_blank" rel="noopener nofollow ugc">下载测试代码</a></p><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">iEngne</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;iEngne</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;sep***n@foxmail.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://raw.githubusercontent.com/iEngne/algorithm_practice/master/sort/bucket_sort.c">&nbsp;&nbsp;参考地址</a></p></div></span>1年前 (2022-04-20)</div></div></li><!-- #comment-## -->
	</ol>
	<div class="pagenav">
			</div>
</div>
<div id="respond" class="no_webshot"> 
		<div class="comment-signarea" style="display:none; padding: 20px 20px;"> 
	<h3 class="text-muted" id="share_code" style="color: #799961;"><i class="fa fa-pencil-square-o" aria-hidden="true"></i> 点我分享笔记</h3>
	<!--
	<p style="font-size:14px;">笔记需要是本篇文章的内容扩展！</p><br>
	<p style="font-size:12px;"><a href="../tougao" target="_blank">文章投稿，可点击这里</a></p>
	<p style="font-size:14px;"><a href="../w3cnote/runoob-user-test-intro.html#invite" target="_blank">注册邀请码获取方式</a></p>
		<h3 class="text-muted"><i class="fa fa-info-circle" aria-hidden="true"></i> 分享笔记前必须<a href="javascript:;" class="runoob-pop">登录</a>！</h3>
		<p><a href="../w3cnote/runoob-user-test-intro.html#invite" target="_blank">注册邀请码获取方式</a></p>-->
	</div>
		
	<form action="/wp-content/themes/runoob/option/addnote.php" method="post" id="commentform" style="display:none;">
		<div class="comt">
			<div class="comt-title">
				<i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i>				<p><a id="cancel-comment-reply-link" href="javascript:;">取消</a></p>
			</div>
			<div class="comt-box">
			<div id="mded"></div>
			
				<div class="comt-ctrl">
					<div class="comt-tips"><input type='hidden' name='comment_post_ID' value='21442' id='comment_post_ID' />
<input type='hidden' name='comment_parent' id='comment_parent' value='0' />
</div>
					<button type="submit" name="submit" id="submit" tabindex="5"><i class="fa fa-pencil" aria-hidden="true"></i> 分享笔记</button>
				</div>
			</div>
		
				
					<div class="comt-comterinfo"> 
						<ul id="comment-author-info">
							<li class="form-inline"><label class="hide" for="author">昵称</label><input class="ipt" type="text" name="author" id="author" value="" tabindex="2" placeholder="昵称"><span class="text-muted">昵称 (必填)</span></li>
							<li class="form-inline"><label class="hide" for="email">邮箱</label><input class="ipt" type="text" name="email" id="email" value="" tabindex="3" placeholder="邮箱"><span class="text-muted">邮箱 (必填)</span></li>
							<li class="form-inline"><label class="hide" for="url">引用地址</label><input class="ipt" type="text" name="url" id="url" value="" tabindex="4" placeholder="引用地址"><span class="text-muted">引用地址</span></li>
						</ul>
					</div>
				
			
		</div>

	</form>
	</div>
<script type="text/javascript">
$(function() {
	//初始化编辑器
	
	var editor = new Simditor({
	  textarea: $('#mded'),
	  placeholder: '写笔记...',
	  upload:false,
	 // upload: {url:'/api/comment_upload_file.php',params: null,fileKey: 'upload_file',connectionCount: 1,leaveConfirm: '文件正在上传，您确定离开?'},
	  defaultImage: 'https://www.runoob.com/images/logo.png',
	  codeLanguages: '',
	  autosave: 'editor-content',
	  toolbar: [  'bold','code','ul','ol','image' ]
	});
	editor.on('selectionchanged', function() {
		$(".code-popover").hide();
	});

	// 提交数据
	$("#share_code").click(function() {
		$(".comment-signarea").hide();
		$("#commentform").show();
		
	});
	$("#user_add_note").click(function() {
		$(".comment-signarea").hide();
		$("#commentform").show();
		$('html, body').animate({
       	    scrollTop: $("#respond").offset().top
    	}, 200);
	});

	// 提交笔记
	var commentform=$('#commentform');
	commentform.prepend('<div id="comment-status" style="display:none;" ></div>');
	var statusdiv=$('#comment-status');
	
	commentform.submit(function(e){
		e.preventDefault();
		var noteContent = editor.getValue();
		// console.log(noteContent);
		noteContent = noteContent.replace(/<pre><code>/g,"<pre>");
		noteContent = noteContent.replace(/<\/code><\/pre>/g,"</pre>");
		
		// 系列化表单数据
		var comment_parent = 0;
		var is_user_logged_in = $("#is_user_logged_in").val();
		var comment_post_ID =  21442;
		var _wp_unfiltered_html_comment = $("#_wp_unfiltered_html_comment").val();
		var comment = noteContent;
		var author = $("#author").val();
		var url = $("#url").val();
		var email = $("#email").val();
		if(isBlank(author) && is_user_logged_in==0) {
			statusdiv.html('<p  class="ajax-error">请输入昵称！</p>').show();
		} else if(isBlank(email)  && is_user_logged_in==0) {
			statusdiv.html('<p  class="ajax-error">请输入邮箱！</p>').show();
		} else {
			// var formdata=commentform.serialize() + "&comment=" + noteContent ;
			// 添加状态信息
			statusdiv.html('<p>Processing...</p>').show();
			// 获取表单提交地址
			var formurl=commentform.attr('action');
			
			// 异步提交
			$.ajax({
					type: 'post',
					url: formurl,
					dataType:'json',
					data: {"comment_parent":comment_parent,"comment_post_ID":comment_post_ID, "_wp_unfiltered_html_comment":_wp_unfiltered_html_comment,"comment":comment,"url":url, "email":email,"author":author},
					error: function(XMLHttpRequest, textStatus, errorThrown){
					statusdiv.html('<p class="ajax-error" >数据不完整或表单提交太快了！</p>').show();
				},
				success: function(data, textStatus){
					if(data.errorno=="0") {
						$("#submit").prop('disabled', true);
						statusdiv.html('<p class="ajax-success" >笔记已提交审核，感谢分享笔记！</p>').show();
						alert('笔记已提交审核，感谢分享笔记！');
					}else{
						statusdiv.html('<p class="ajax-error" >'+data.msg+'</p>').show();
					}
					commentform.find('textarea[name=comment]').val('');
				}
			});
			setTimeout(function(){
		        $("#submit").prop('disabled', false);
		    }, 10*1000);
		}
		return false;

	});
	$(".comt-author").click(function() {
		href = $(this).children("a").attr("href");
		if(href.indexOf("/note/")!=-1) {
			var win = window.open(href, '_blank');
  			win.focus();
		}
	});
	$(".comt-meta span").hover(function(){
		$(this).children(".tooltip").css({ "opacity": 1, "pointer-events": "auto"});
	},function(){
		$(this).children(".tooltip").removeAttr("style");
	});
	/*
	$(".wrapper i").hover(function(){
		$(this).siblings(".tooltip").css({ "opacity": 1, "pointer-events": "auto"});
	},function(){
		$(this).siblings(".tooltip").css({ "opacity": 0, "pointer-events": "auto"});
	});
	*/
	//Upvote.create('runoobvote-id', {callback: vote_callback});
	var ajaxurl = 'https://www.runoob.com/wp-admin/admin-ajax.php';
	var callback = function(data) {
		//console.log($('#runoobvote-id').upvote('upvoted'));
		//console.log($('#runoobvote-id').upvote('downvoted'));
		//console.log(data);
		_vote_action = data.action;
		id_arr = data.id.split('-');
		um_id= id_arr[2];
		//console.log(um_id);
		
		var re = /^[1-9]+/;
		if (re.test(um_id)) { 
			var ajax_data = {
				_vote_action: _vote_action,
				action: "pinglun_zan",
				um_id: um_id,
				um_action: "ding"
			};
			//console.log(ajax_data);
			$.post(ajaxurl,ajax_data,function(status){
				//if(status.vote_num>999) {
				//	_voteHtml = '<span style="display: block; text-align: center;font-size: 20px; color: #6a737c; margin: 8px 0;">'+kFormatter(status.vote_num) +'</span>';
				//	$("#runoobvote-id-" + um_id + " .count").hide().after(_voteHtml);
				//}
				
			});
		}
	};
	if($('#comments').length && $('.upvotejs').length){
		$('.upvotejs').upvote({id: 21442, callback: callback});
	
		$.post(ajaxurl,{"action":"pinglun_zan","postid":21442},function(data){  
			$(data).each(function(key,value) {
				$("#runoobvote-id-" + value.commid + " .upvote").addClass(value.upvotejs_class);
				$("#runoobvote-id-" + value.commid + " .downvote").addClass(value.downvote_class);
				$("#runoobvote-id-" + value.commid + " .count").text(value.upvote_count);
			})
		},'json');
		
	}
	
	
});
function isBlank(str) {
    return (!str || /^\s*$/.test(str));
}
function kFormatter(num) {
	// return num;
    return Math.abs(num) > 999 ? Math.sign(num)*((Math.abs(num)/1000).toFixed(1)) + 'k' : Math.sign(num)*Math.abs(num)
}

</script>

<link rel="stylesheet" href="../0/qa.css?1.44">
<link rel="stylesheet" type="text/css" href="../0/simditor.min.css" />
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
			<div class="article-heading-ad" id="w3cnote-ad728">
			<script async src=""></script>
			<!-- 移动版 自动调整 -->
			<ins class="adsbygoogle"
			     style="display:inline-block;min-width:300px;max-width:970px;width:100%;height:90px"
			     data-ad-client="ca-pub-5751451760833794"
			     data-ad-slot="1691338467"
			     data-ad-format="horizontal"></ins>
			<script>
			(adsbygoogle = window.adsbygoogle || []).push({});
			</script>
			</div>
			<style>
@media screen and (max-width: 768px) {
	#w3cnote-ad728 {
		display: none;
	}
}
p.note-author {
    border-bottom: 1px solid #ddd;
    font-size: 18px;
    font-weight: bold;
    color: #78a15a;
    padding-bottom: 2px;
    margin-bottom: 4px;
}
</style>
<script>
var aid = 21442;
</script>
	</div>
		
	</div>
	<div class="listcol last right-column">

	<script type="text/javascript">
jQuery(document).ready(function ($){
	var total = $(".membership li").length;
	var left_list = '';
	href = window.location.href;
	
	$(".membership li").each(function(index, value){

		left_list += $(this).html();

		cur_href = $(this).find("a").attr("href");
		cur_obj = $(this);
		
		if(href.match(cur_href) != null) {
			if(index==0) {
				$(".previous-design-link").hide();
			}
			if(index==(total-1)) {
				$(".next-design-link").hide();
			}
			prev_href = cur_obj.prev("li").find("a").attr("href");
			prev_title = cur_obj.prev("li").find("a").attr("title");

			next_href = cur_obj.next("li").find("a").attr("href");
			next_title = cur_obj.next("li").find("a").attr("title");
			if(prev_title) {
				$(".previous-design-link a").attr("href", prev_href);
				$(".previous-design-link a").attr("title", prev_title);
				$(".previous-design-link a").text(prev_title);
			} else {
				$(".previous-design-link").html("");
			}

			if(next_title) {
				$(".next-design-link a").attr("href", next_href);
				$(".next-design-link a").attr("title", next_title);
				$(".next-design-link a").text(next_title);
			} else {
				$(".next-design-link").html("");
			}
		}
	});

	$("#leftcolumn").html(left_list);
});
	</script>
	<div class="sidebar-box cate-list">
	<div class="sidebar-box recommend-here list-link">
	<a href="javascript:void(0);">算法系列</a>	</div>
	
	<ul class="membership">
		
	<li><a target="_top" data-id="21423" title="1.0 十大经典排序算法" href="../w3cnote/ten-sorting-algorithm.html" >1.0 十大经典排序算法</a></li>
	
		
	<li><a target="_top" data-id="21425" title="1.1 冒泡排序" href="../w3cnote/bubble-sort.html" >1.1 冒泡排序</a></li>
	
		
	<li><a target="_top" data-id="21427" title="1.2 选择排序" href="../w3cnote/selection-sort.html" >1.2 选择排序</a></li>
	
		
	<li><a target="_top" data-id="21429" title="1.3 插入排序" href="../w3cnote/insertion-sort.html" >1.3 插入排序</a></li>
	
		
	<li><a target="_top" data-id="21431" title="1.4 希尔排序" href="../w3cnote/shell-sort.html" >1.4 希尔排序</a></li>
	
		
	<li><a target="_top" data-id="21433" title="1.5 归并排序" href="../w3cnote/merge-sort.html" >1.5 归并排序</a></li>
	
		
	<li><a target="_top" data-id="21435" title="1.6 快速排序" href="../w3cnote/quick-sort-2.html" >1.6 快速排序</a></li>
	
		
	<li><a target="_top" data-id="21437" title="1.7 堆排序" href="../w3cnote/heap-sort.html" >1.7 堆排序</a></li>
	
		
	<li><a target="_top" data-id="21440" title="1.8 计数排序" href="../w3cnote/counting-sort.html" >1.8 计数排序</a></li>
	
		<li>
	1.9 桶排序	</li>
	
		
	<li><a target="_top" data-id="21445" title="1.10 基数排序" href="../w3cnote/radix-sort.html" >1.10 基数排序</a></li>
	
	</ul></div>	</div>
</div>


<!-- 底部 -->
<div id="footer" class="mar-t50">
   <div class="runoob-block">
    <div class="runoob cf">
     <dl>
      <dt>
       在线实例
      </dt>
      <dd>
       &middot;<a target="_blank" href="../html/html-examples.html">HTML 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../css/css-examples.html">CSS 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../js/js-examples.html">JavaScript 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../ajx/ajax-examples.html">Ajax 实例</a>
      </dd>
       <dd>
       &middot;<a target="_blank" href="../jquery/jquery-examples.html">jQuery 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../xml/xml-examples.html">XML 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../java/java-examples.html">Java 实例</a>
      </dd>
     
     </dl>
     <dl>
      <dt>
      字符集&工具
      </dt>
      <dd>
       &middot; <a target="_blank" href="../charsets/html-charsets.html">HTML 字符集设置</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="../tags/html-ascii.html">HTML ASCII 字符集</a>
      </dd>
     <dd>
       &middot; <a target="_blank" href="https://c.runoob.com/front-end/6939/">JS 混淆/加密</a>
      </dd> 
      <dd>
       &middot; <a target="_blank" href="https://c.runoob.com/front-end/6232/">PNG/JPEG 图片压缩</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="../tags/html-colorpicker.html">HTML 拾色器</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="..//c.runoob.com/front-end/53">JSON 格式化工具</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="..//c.runoob.com/front-end/6680/">随机数生成器</a>
      </dd>
     </dl>
     <dl>
      <dt>
       最新更新
      </dt>
                   <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imread.html" title="Matplotlib imread() 方法">Matplotlib imre...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imsave.html" title="Matplotlib imsave() 方法">Matplotlib imsa...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imshow.html" title="Matplotlib imshow() 方法">Matplotlib imsh...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-hist.html" title="Matplotlib 直方图">Matplotlib 直方图</a>
      </dd>
              <dd>
       &middot;
      <a href="../python3/python-func-object.html" title="Python object() 函数">Python object()...</a>
      </dd>
              <dd>
       &middot;
      <a href="../python3/python-ai-draw.html" title="Python AI 绘画">Python AI 绘画</a>
      </dd>
              <dd>
       &middot;
      <a href="../w3cnote/cursor-editor.html" title="神辅助 Cursor 编辑器，加入 GPT-4 让编码更轻松！">神辅助 Cursor ...</a>
      </dd>
             </dl>
     <dl>
      <dt>
       站点信息
      </dt>
      <dd>
       &middot;
       <a target="_blank" href="mailto:admin@runoob.com" rel="external nofollow">意见反馈</a>
       </dd>
      <dd>
       &middot;
      <a target="_blank" href="../disclaimer">免责声明</a>
       </dd>
      <dd>
       &middot;
       <a target="_blank" href="../aboutus">关于我们</a>
       </dd>
      <dd>
       &middot;
      <a target="_blank" href="../archives">文章归档</a>
      </dd>
    
     </dl>
    
     <div class="search-share">
      <div class="app-download">
        <div>
         <strong>关注微信</strong>
        </div>
      </div>
      <div class="share">
      <img width="128" height="128" src="/wp-content/themes/runoob/assets/images/qrcode.png" />
       </div>
     </div>
     
    </div>
   </div>
   <div class="w-1000 copyright">
     Copyright &copy; 2013-2023    <strong><a href="../" target="_blank">菜鸟教程</a></strong>&nbsp;
    <strong><a href="../" target="_blank">runoob.com</a></strong> All Rights Reserved. 备案号：<a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn/">闽ICP备15012807号-1</a>
   </div>
  </div>
  <div class="fixed-btn">
    <a class="go-top" href="javascript:void(0)" title="返回顶部"> <i class="fa fa-angle-up"></i></a>
    <a class="qrcode"  href="javascript:void(0)" title="关注我们"><i class="fa fa-qrcode"></i></a>
    <a class="writer" style="display:none" href="javascript:void(0)"   title="标记/收藏"><i class="fa fa-star" aria-hidden="true"></i></a>
    <!-- qrcode modal -->
    <div id="bottom-qrcode" class="modal panel-modal hide fade in">
      <h4>微信关注</h4>
      <div class="panel-body"><img alt="微信关注" width="128" height="128" src="/wp-content/themes/runoob/assets/images/qrcode.png"></div> 
    </div>
  </div>

 <div style="display:none;">
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-84264393-2"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-84264393-2');
</script>
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?3eec0b7da6548cf07db3bc477ea905ee";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>

</div>
<script>
window.jsui={
    www: 'https://www.runoob.com',
    uri: 'https://www.runoob.com/wp-content/themes/runoob'
};
</script>

<script src=""></script>
<script src=""></script>

</body>
</html>